#!/usr/bin/python
# -*- coding:UTF-8 -*-

#本文介绍的全文搜索引擎，允许人们在大量文档中搜索一系列单词,并根据文档与这些单词的相关程度对结果进行排名
#下面会完整地介绍一个搜索引擎的构造过程,利用它来对一组文档建立索引(index),并向你提供某些进一步的建议
#主要包括:如何检索网页(crawl)、建立索引、对网页进行搜索、多种不同方式对搜索结果进行排名
#主要步骤包括：
#首先：找到一种搜集文档的方法。
#      1、通常会涉及到针取(从互联网上)先从一小组网页开始，然后再根据网页内的链接逐步追踪其他的网页，
#      2、需要我们在一组固定数量的文档范围内进行搜集，这些文档可能来自于某个公司的内部网络
#第二步:我们需要为这些文档建立索引，通常我们须要建立一张大的表，表中包含了文档所有不同单词的位置信息。
#       取决于具体的应用，文档本身不一定非要保存于数据库中
#       索引信息只须简单地保存一个指向文档所在位置引用即可（例如文件系统路径或URL)
#第三步：通过查询返回一个经过排序的文档列表，一旦建立了索引，根据经定单词或词组来获取文档就变得非常简单，
#核心能力：结果的排列方式。（通过不同的方式，改变网页排名次序）
#          本章涉及到的几种基于网页内容的度量方法
#             1、基于网页内容的度量方法（单词频度）
#             2、基于网页外部信息的度量方法（PageRank,考查其他网页对当前网页的引用情况）
#             3、神经网络（通过了解人们在得到搜索结果以后都点击了哪些链接，将搜索过程与搜索结果关联起来，
#                来改变搜索结果的排列顺序，更好地反映人们过去的点击情况
import urllib,urllib.request,urllib.parse
from bs4 import BeautifulSoup
import sqlite3 as sqlite
import re

# 构造一个单词列表,这些单词将被忽略
ignorewords = set(['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it'])


#爬虫类和相关的方法
#实现原理：该程序将接受一小组等待建立索引的网页，然后再根据这些网页内部的链接
#而找到其他的网页,依此类推。这一过程被称为检索或蛛行(spidering)
class crawler:
    # 初始化crawler类并传入数据库名称
    def __init__(self, dbname):
        self.con = sqlite.connect(dbname)

    def __del__(self):
        self.con.close()

    def dbcommit(self):
        self.con.commit()

    # 辅助函数,用于获取条目的id,并且如果条目不存在,就将其加入数据库中
    # 作用是返回某一条目的ID
    def getentryid(self, table, field, value, createnew=True):
        cur = self.con.execute("select rowid from %s where %s='%s'" % (table, field, value))
        res = cur.fetchone()
        if res == None:
            cur = self.con.execute("insert into %s (%s) values ('%s')" % (table, field, value))
            return cur.lastrowid
        else:
            return res[0]

    # 为每个网页建立索引
    # 流程：该方法首先得到一个出现于网页中的单词的列表，然后,它会将网页及所有单词加入索引
    #       在网页和单词之间建立关联，并保存单词在文档中出现的位置，
    #       本例中：单词的位置就是其在列表中的索引号
    def addtoindex(self, url, soup):
        if self.isindexed(url): return
        print('Indexing %s' % url)

        # 获取每个单词
        text = self.gettextonly(soup)
        words = self.separatewords(text)

        # 得到URL的id
        urlid = self.getentryid('urllist', 'url', url)

        # 将每个单词与该url关联
        for i in range(len(words)):
            word = words[i]
            if word in ignorewords: continue
            wordid = self.getentryid('wordlist', 'word', word)
            self.con.execute("insert to wordlocation(urlid,wordif,location) \
												values (%d,%d,%d)" % (urlid, wordid, i))

    # 从一个HTML网页中提取文字（不带标签的）
    # 功能：首先从网页中提取所有的文字部分,为此,我们可以对文本节点进行搜索,搜集所有的文字内容
    # 返回：返回一个长字符串，其中包含了网页中的所有文字，它以递归向下的方式对HTML文档对象
    #       模型进行遍历，并找出其中的文本节点（为了利于销后某些度量的计算，在这一阶段保留
    #       各章节的前后顺序是很重要的。
    def gettextonly(self, soup):
        v = soup.string
        if v == None:
            c = soup.contents
            resulttext = ' '
            for t in c:
                subtext = self.gettextonly(t)
                resulttext += subtext + '\n'
            return resulttext
        else:
            return v.strip()

    # 根据任何非空白字符进行分词处理
    # 该函数将字符串拆分成一组独立的单词，以便我们将其加入到索引之中
    # 核心点：本章的示例中,将任何非字母或非数字的字符作为分隔符就已经足够了
    #         我们还可以利用正则表达式来进行分词
    #         还会涉及到词干提取算法(stemming algorithm)去除单词的后缀,词干提取算法试图将单词转换成对应的词干
    def separatewords(self, text):
        splitter = re.compile('\\W*')
        return [s.lower() for s in splitter.spli(text) if s != '']

    # 如果url已经建过索引,则返回true
    def isindexed(self, url):
        u = self.con.execute("select rowid from urllist where url='%s'" % url).fetchone()
        if u != None:
            # 检查它是否已经被检索过了
            v = self.con.execute('select * from wordlocation where urlid=%d' % u[0]).fetchone()
            if v != None: return True

        return False

    # 添加一个关联两个网页的链接
    def addlinkref(self, urlFrom, urlTo, linkText):
        pass

    # 从一小组网页开始进行广度优先搜索,直至某一给定深度
    # 期间为网页建立索引
    def crawl(self, pages, depth=2):
        for i in range(depth):
            newpages = set()
            for page in pages:
                try:
                    c = urllib.request.urlopen(page)
                except:
                    print("Could not open %s" % page)
                    continue
                soup = BeautifulSoup(c.read())
                #针对每个网页调用addtoindex函数
                self.addtoindex(page, soup)

                #通过Beautiful Soup函数获取网页中的所有链接，并将这些链接加入到一个名为newpages的集合中，在循环结束之前
                #我们将newpages赋给pages,而后这一过程再次循环
                links = soup('a')
                for link in links:
                    if ('href' in dict(link.attrs)):
                        url = urllib.parse.urljoin(page, link['href'])
                        if url.find("'" != -1): continue
                        url = url.split('#')[0]  # 去掉位置部分
                        if url[0:4] == 'http' and not self.isindexed(url):  #isindexed决定一个网页在被加入newpages之前是否已经在近期做过了索引
                            newpages.add(url)
                        linkText = self.gettextonly(link)
                        self.addlinkref(page, url, linkText)

                self.dbcommit()
            pages = newpages


    
    #创建数据库表
    #我们需要建立5张表,
    #					第一张表(urllist：rowid,url)保存的是已经过索引的URL列表
    #         第二张表(wordlist: rowid,word)保存的是单词列表
    #         第三张表(wordlocation:urlid,wordid,location) 保存的是单词在文档中所处位置的列表
    #         第四张表(link: rowid,fromid,toid) 保存了两个URL ID信息,指明从一张表到另一张表的链接关系
    #         第五张表(linkwords: wordid,linkid) 利用字段wordid和linkid记录了哪些单词与链接实际相关。
    #         第四、五张表保存介于文档之间的链接信息,所有的SQLite中的表默认都有一个名为rowid的字段。
    def createindextables(self):
        self.con.execute('create table urllist(url)')
        self.con.execute('create table wordlist(word)')
        self.con.execute('create table wordlocation(urlid,wordid,location)')
        self.con.execute('create table link(fromid integer,toid integer)')
        self.con.execute('create table linkwords(wordid,linkid)')
        self.con.execute('create index wordidx on wordlist(word)')
        self.con.execute('create index urlidx on urllist(url)')
        self.con.execute('create index wordurlidx on wordlocation(wordid)')
        self.con.execute('create index urltoidx on link(toid)')
        self.con.execute('create index urlfromidx on link(fromid)')
        self.dbcommit()

#===========搜索引擎======================================
class searcher:
    def __init__(self, dbname):
        self.con = sqlite.connect(dbname)

    def __del__(self):
        self.con.close()
		
		#功能：查询函数，接受一个查询字符串作为参数，并将其拆分为多个单词，然后构造一个SQL查询，
		#      只查找那些包含所有不同单词的URL,
    def getmatchrows(self, q):
        # 构造查询的字符串
        fieldlist = 'w0.urlid'
        tablelist = ''
        clauselist = ''
        wordids = []

        # 根据空格拆分单词
        words = q.split(' ')
        tablenumber = 0

        for word in words:
            # 获取单词的ID
            wordrow = self.con.execute("select rowid from wordlist where word='%s'" % word).fetchone()
            if wordrow != None:
                wordid = wordrow[0]
                wordids.append(wordid)
                if tablenumber > 0:
                    tablelist += ','
                    clauselist += ' and '
                    clauselist += 'w%d.urlid=w%d.urlid and ' % (tablenumber - 1, teblenumber)
                fieldlist += ',w%d.location' % tablenumber
                tablelist += 'wordlocation w%d' % tablenumber
                clauselist += 'w%d.wordid=%d' % (tablenumber, wordid)
                tablenumber += 1

        # 根据各个组分,建立查询
        fullquery = 'select %s from %s where %s' % (fieldlist, tablelist, clauselist)
        cur = self.con.execute(fullquery)
        rows = [row for row in cur]
        return rows, wordids

    # 基于内容的排名,该方法接受查询请求,将获取到的行集置于字典中,并以格式化列表的形式显示输出
    def getscoredlist(self, rows, wordlist):
        totalscores = dict([row[0], 0] for row in rows)

        # 此处是稍后放置评价函数的地方
        # weights=[]
        weights = [(1.0, self.frequencyscore(rows))]
        # weights = [(1.0,self.locationscore(rows))]

        for (weight, scores) in weights:
            for url in totalscores:
                totalscores[url] += weight * scores[url]

        return totalscores

    def geturlname(self, id):
        return self.con.execute("select url from urllist where rowid=%d" % id).fetchone()[0]
		
		#query方法现在还没有对结果进行任何评价,不过它的确输出了URL和代表评价值的占位符
    def query(self, q):
        rows, wordids = self.getmatchrows(q)
        scores = self.getscoredlist(rows, wordids)
        rankedscores = sorted([(score, url) for (url, score) in scores.items()], reverse=1)
        for (score, urlid) in rankedscores[0:10]:
            print('%f\t%s' % (score, self.geturlname(urlid)))

    # 归一化函数
    # 所有评价方法返回的都是包含URL ID和数据评价值的字典,含事情变得复杂化的是：有的评价方法分值越大越好,
    # 而有的则分值越小越好。我们需要一种对结果进行归一化处理的方法
    # 功能说明：归一化函数将接受一个包含ID与评价值的字典，并返回一个带有相同ID，而评价值则介于0与1
    #           之间的新字典。我们所要做的全部工作，就是将评价值列表传入该函数，并指明数值越小越好
    #           还是越大越好
    def normalizescores(self, scores, smallIsBetter=0):
        vsmall = 0.00001  # 避免被零整除
        if smallIsBetter:
            minscore = min(scores.values())
            return dict([(u, float(minscore) / max(vsmall, 1)) for (u, l) in scores.items()])
        else:
            maxscore = max(scores.values())
            if maxscore == 0: maxscore = vsmall
            return dict([(u, float(c) / maxscore) for (u, c) in scores.items()])

#============网页内容处理方法======================
    # 单词频度函数
    # 功能说明：该方法以单词频度作为度量手段,根据查询条件的单词在网页中出现的次数对网页进行评价    
    def frequencyscore(self, rows):
        counts = dict([(row[0], 0) for row in rows])
        for row in rows: counts[row[0]] += 1
        return self.normalizescores(counts)

    # 文档位置
    # 另一个判断网页与查询条件相关程度的简单度量方法，是搜索单词在网页中的位置,
    # 通常，如果一个网页现待搜索的单词相关，则该单词就更有可能在靠近网页开始处的
    # 位置出现，或者甚至出现在标题中。
    # 请记住：行集中每一行的第一项是URL ID,后面紧跟的是所有待查单词的位置信息，
    #         针对每一行,该方法将会计算所有单词的位置之和，并将这一结果与当前的最
    #         佳结果进行对比判断，并将结果传入归一化处理函数
    def locationscore(self, rows):
        locations = dict([(row[0], 1000000) for row in rows])
        for row in rows:
            loc = sum(row[1:])
            if loc < locations[row[0]]: locations[row[0]]= loc

            return
            self.normalizescores(locations, smallIsBetter=1)

    # 单词距离
    # 解决多词查询时,人们时常会关注于那些在概念意义上与这些单词有关联的网页,这
    # 要比大多数搜索引擎所支持的以引号相括的短语搜索更为宽松。（而在此处,这种度量方
    # 法将允许单词顺序不一，也允许单词夹带其他的单词)
    def distancescore(self, rows):
        # 如果仅有一个单词,则得分都一样
        if len(rows[0]) <= 2: return dict([(row[0], 1.0) for row in rows])

        # 初始化字典,并填入一个很大的数
        mindistance = dict([(row[0], 1000000) for row in rows])

        for row in rows:
            dist = sum([abs(row[i] - row[i - 1]) for i in range(2, len(row))])
            if dist < mindistance[row[0]]: mindistance[row[0]] = dist
        return self.normalizescores(mindistance, smallIsBetter=1)

#==================网页与外部网页之间的关联==============================================


    # 简单计数
    # 处理外部回指链接最为简单的做法，是在每个网页上统计链接的数目,并将链接总数作为针对网页的度量
    # 科研论文就经常采用这样的方式，
    def inboundlinkscore(self, rows):
        uniqueurls = dict([(row[0],1) for row in rows])
        inboundcount = dict([(u, self.con.execute('select count(*) from link where toid=%d' % u).fetchone()[0]) for u in uniqueurls])
        return self.normalizescores(inboundcount)


    def calculatepagerank(self, iterations=20):
        # 清除当前的PageRank表
        self.con.execute('DROP TABLE IF EXISTS pagerank')
        self.com.execute('create table pagerank(urlid primary key,score)')

        # 初始化每个url,令其PageRank值为1
        self.con.execute('INSERT INTO pagerank SELECT rowid,1.0 FROM urllist')
        self.dbcommit()

        for i in range(iterations):
            print("Iteration %d" % (i))
            for (urlid,) in self.con.execute('SELECT rowid FROM urllist'):
                pr = 0.15

                # 循环遍历指向当前网页的所有其他网页
                for (linker,) in self.con.execute('select distinct fromid form link where toid=%d' % urlid):
                    # 得到链接源对应网页的PageRank值
                    linkingpr = self.con.execute('select score from pagerank where urlid=%d' % linker).fetchone()[0]

                    # 根据链接源，求得总的链接数
                    linkingcount = self.con.execute('select count(*) from link where fromid=%d' % linker).fetchone()[0]
                    pr += 0.85 * (linkingpr / linkingcount)
                self.con.execute('update pagerank set score=%f where urlid=%d' % (pr, urlid))
            self.dbcommit()


    def pagerankscore(self, rows):
        pageranks = dict([(row[0], self.con.execute('select score from pagerank where urlid=%d' % row[0]).fetchone()[0]) for row in rows])
        maxrank = max(pageranks.values())
        normalizedscores = dict([(u, float(1) / maxrank) for (u, l) in pageranks.items()])
        return normalizedscores

    # 利用链接文本
    def linktextscore(self, rows, wordids):
        linkscores = dict([(row[0], 0) for row in rows])
        for wordid in wordids:
            cur = self.con.execute('select link.fromid,link.toid from linkwords,link where wordid = %d and linkwords.linkid = link.rowid ' % wordid)
            for (fromid, toid) in cur:
                if toid in linkscores:
                    pr = self.con.execute('select score from pagerank where urlid=%d' % fromid).fetchone()[0]
                    linkscores[toid] += pr

        maxscore = max(linkscores.values())
        normalizedscores = dict([(u, float(1) / maxscore) for (u, l) in linkscores.items()])
        return normalizedscores